# 
# Created by francklinson on 2021/10/12 AT 11:00.
#
from typing import List


class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        n = len(nums)
        nums.sort()
        minIndex = 0
        while k > 0:
            nums[minIndex] = -nums[minIndex]
            if minIndex < n - 1 and nums[minIndex] > nums[minIndex + 1]:
                # 变号后比下一个数更大  变更指针位置
                minIndex += 1
            k -= 1
        ans = 0
        for i in range(n):
            ans += nums[i]
        return ans


class Solution2:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        nums.sort(key=lambda x: abs(x), reverse=True)
        for i in range(len(nums)):
            if nums[i] < 0 and k > 0:
                nums[i] *= -1
                k -= 1
        if k % 2 == 1:
            nums[-1] *= -1
        return sum(nums)


if __name__ == '__main__':
    sol = Solution2()
    print(sol.largestSumAfterKNegations(nums=[4, 2, 3], k=1))
    print(sol.largestSumAfterKNegations(nums=[3, -1, 0, 2], k=3))
    print(sol.largestSumAfterKNegations(nums=[2, -3, -1, 5, -4], k=2))
